1. Field of the Invention
The present invention relates to optimizing compilers for computer programs, and more specifically, to retargeting optimized code by matching tree patterns in directed acyclic graphs.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found in Section 9 of the "Detailed Description of the Preferred Embodiment." Each of these publications is incorporated by reference herein.)
Programmers write computer programs in high level languages such as assembler language, COBOL, FORTRAN, C, C++, etc. A group of statements written in a language is referred to as source code. Before the source code can be executed, the statements within the source code must be transformed to object code.
Much work has been devoted to building optimizing compilers that generate optimized object code. However, it is often difficult to modify an optimizing compiler built for one target processor to generate optimized object code for a different target processor.
There is also the problem of using tree pattern matching systems (e.g., TWIG [1], BEG [14], BURS [8, 17, 24]) to perform retargetable code generation after code optimization.
In the tree pattern matching approach, the target instruction set is specified by a set of tree patterns defined on the input intermediate language (IL). Analogous to the generation of parsing tables, the tree patterns are translated to pattern matching tables at "compiler-compile" time. An efficient dynamic programming method then uses these tables at compile-time to obtain a minimum-cost parse for each input tree of IL instructions. Automating the generation of pattern matching tables and the process of finding a minimum-cost tree parse leads to significant savings in the programming effort and complexity required for building a code generator. (The terms "tree parsing" and "tree pattern matching" are used interchangeably.)
However, there is a basic mismatch between the ILs that have been used for tree pattern matching and the ILs used by industry-strength optimizing back-ends. ILs used for tree pattern matching are typically structured as a list of expression trees. ILs used in industry-strength optimizing back-ends instead typically use a structure such as quadruples [2] or RTL [21] so as to get the maximum flexibility in code optimization. The optimized code for a basic block in such an IL is structured more generally as a Directed Acyclic Graph (DAG) of instruction nodes [2] defined by true dependences and augmented by anti, output and memory dependences [25]. Since DAGs cannot be fed into a retargetable code generator based on tree pattern matching, the challenge is to identify trees within each basic block DAG so that tree pattern matching can be used to generate correct and efficient target code from the optimized code for a basic block.